#include <iostream>

using namespace std;

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LinkNode;

int main(){
    void createListR(LinkNode *&con_list,ElemType array[],int n);
    void dispList(LinkNode *con_list);
    void destroyList(LinkNode *&con_list);
    void listAndFuction(LinkNode *con_list1,LinkNode *con_list2,LinkNode *&new_list);
    void showArray(int array[],int n);

        ElemType arrayA[]={1,2,3,4,5,6,7,8,9,10},arrayB[]={3,4,7,11,56,23,21,102,9,5};
    LinkNode *A,*B,*new_A;
    int aLength,bLength;
    cout<<"用于初始化链表的数组（各有10个）分别为：\n数组A为："<<endl;
    showArray(arrayA,10);
    cout<<"数组B为："<<endl;
    showArray(arrayB,10);

    cout<<"请输入你想要的链表A和链表B的长度："<<endl;
    cin>>aLength>>bLength;
    if ((aLength>0&&aLength<=10)&&(bLength>0&&bLength<=10)) {
        createListR(A, arrayA, aLength);
        createListR(B, arrayB, bLength);

        puts("集合A:");
        dispList(A);
        puts("\n集合B:");
        dispList(B);


        listAndFuction(A, B, new_A);
        puts("\nA∪B:(A与B的并集)");
        dispList(new_A);

        destroyList(A);
        destroyList(B);
        destroyList(new_A);
        cout<<"成功运行（￣︶￣）↗　"<<endl;
    }
    else
        cout<<"输入错误o((⊙﹏⊙))o."<<endl;


    return 0;
}
void showArray(int array[],int n){
    for (int i = 0; i <n ; i++) {
        printf("%d\t",array[i]);
    }
//    puts("\n");
printf("\n");
}
void initList(LinkNode *&con_list){
//    用于初始化链表
    con_list=(LinkNode *)malloc(sizeof(LinkNode));
    con_list->next=NULL;
}
void createListR(LinkNode *&con_list,ElemType array[],int n){
//    运用尾插法构造链表
    LinkNode *s,*r;
    con_list=(LinkNode *)malloc(sizeof(LinkNode));
    r=con_list;
    for (int i = 0; i <n ; i++) {
        s=(LinkNode *)malloc(sizeof(LinkNode));
        s->data=array[i];
        r->next=s;
        r=s;
    }
    r->next=NULL;
}
void dispList(LinkNode *con_list){
//    输出链表
    LinkNode *p=con_list->next;
    while (p!=NULL){
        printf("%d\t",p->data);
        p=p->next;
    }
}
void listAndFuction(LinkNode *con_list1,LinkNode *con_list2,LinkNode *&new_list){
//    将两个集合链表进行并运算，并返回新的链表
    int listLength(LinkNode *con_list);
    void initList(LinkNode *&con_list);
    bool listInsert(LinkNode *&con_list,int i,ElemType e);
    bool getElem(LinkNode *con_list,int index,ElemType &e);
    int LocateElem(LinkNode *L,ElemType e);

    int length;
    ElemType e;
    initList(new_list);
   for (int i = 1; i <=listLength(con_list1) ; i++) {
        getElem(con_list1,i,e);
        listInsert(new_list,listLength(new_list)+1,e);
    }
    for (int i = 1; i <=listLength(con_list2) ; i++) {
        getElem(con_list2,i,e);
        if (LocateElem(con_list1,e)==0)
            listInsert(new_list,listLength(new_list)+1,e);
    }


    }

bool listInsert (LinkNode *&L, int i, ElemType e){
    int j = 0;
    LinkNode *p = L,*s;          //p指向头结点，j置为0
    while ( j<i-1 && p != NULL)	//查找第i-1个结点
    {	j++;
        p = p->next;
    }
    if (p == NULL)	//未找到第i-1个结点，返回false
        return false;
    else	//找到第i-1个节点*p,插入新结点并返回true
    {	s = (LinkNode *)malloc(sizeof(LinkNode));
        s->data = e;		//创建新结点*s，其data域置为e
        s->next = p->next;	//将*s插入到*p之后
        p->next = s;
        return true;
    }
}
void destroyList(LinkNode *&con_list){
//    销毁链表，并释放空间
    LinkNode *pre=con_list,*p=con_list->next;
    while (p!=NULL){
        free(pre);
        pre=p;
//        cout<<p->data<<endl;
        p=p->next;
    }
    free(pre);
}
int listLength(LinkNode *con_list){
//    用于返回链表的长度
    int n=0;
    LinkNode *p=con_list;
    while (p->next!=NULL){
        n++;
       p=p->next;
    }
    return n;
}
bool getElem(LinkNode *con_list,int index,ElemType &e){
//    用于得到链表第index个元素,指逻辑上的下标，而不是物理上的下标
    int j=0; //用于遍历链表
    LinkNode *p=con_list;
    if(index <=0)
        return false;
    while (j<index&&p!=NULL){
        j++;
        p=p->next;

    }
    if (p==NULL)
        return false;
    else
    {
        e=p->data;
        return true;
    }
}
int LocateElem(LinkNode *L,ElemType e)
{
//    查找是否含有元素e,没有返回0，有则返回序号
    int i=1;
    LinkNode *p = L->next;		//p指向开始结点，i置为1
    while (p != NULL && p->data != e)
    {        p = p->next;  //查找data值为e的结点，其序号为i
        i++;
    }
    if (p == NULL)	//不存在元素值为e的结点，返回0
        return(0);
    else		//存在元素值为e的结点，返回其逻辑序号i
        return(i);
}